Context Free Language 2

CFG 2

Methods for Transforming Grammars

• 定理6.1

  

  • 代換 variable

• 有效的代換規則

  

NULLable Production

• 代換 null

  

• Example

  

  • 把null production代換掉

    

  • 多個production的例子

Unit production

• Production 兩端都只有一個variable

  
  

  • 直接移除

    

  • 畫出關係圖
    • P1: B產生自S
    • P2: A產生自B
    • P3: B產生自A

      

    • 根據關係圖 拓展

Useless Production

• 不終結的Production

  

• 不抵達的Production

  

• 如何移除

  
  
  
  
  

移除順序

• 順序

  

Two Important Normal Form

• CNF

  

  • Example

    

  • 如何轉換成CNF

    
    

    • Terminal 換成 Variable

      

    • 兩個Variable一組 由一個新的Variable生成…
  • 不包含 null的production 都可以換成等價的CNF

    

  • 作法

    

  • CNF 很適合Parsing

    

• GNF

  

  • Example

    

  • CFG 可以轉換成 GNF

    

  • GNF 適合Parsing 但很難找出來

    

A Membership Algorithm for CFGs*

• 如何確定一個字串屬於當前的CFG

  

• CYK

  

  • Example

    
    

    • 從每個index 向後推算